class Solution {
private:
    int k;
    vector<int> dfs(TreeNode* root){
        vector<int> res(k + 1, 0);
        if(!root)return res;
        vector<int> l = dfs(root->left);
        vector<int> r = dfs(root->right);
        res[0] = *max_element(l.begin(), l.end()) + *max_element(r.begin(), r.end());
        for(int i = 1; i <= k; i++){
            for(int j = 0; j < i; j++){
                res[i] = max(res[i], l[j] + root->val + r[i - j - 1]);
            }
        }
        return res;
    }
public:
    int maxValue(TreeNode* root, int k) {
        this->k = k;
        vector<int> ans = dfs(root);
        return *max_element(ans.begin(), ans.end());
    }
};

//2021.4.10
